数据结构 稀疏数组
稀疏数组是什么？
稀疏数组（Sparse Array）就是数组中，大部分的元素值都未被使用（或都为0），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了解决这问题，并且不影响数组中原 有的元素值，我们采用了一种压缩的方式来 表示稀疏数组的内容。
如图二维数组所示，有大部分的空间是无用的。
而稀疏数组的处理方法是：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
上面使用稀疏数组进行压缩。
其中在稀疏数组中第一部分所记录的是 原数组的列数和行数以及元素使用的个数、第二部分所记录的是原数组中元素的位置和内容。（不过在实际应用中有些情况省略掉第一部分）
如上的第三行
3 0 1
就表示它位于：行 3，列 0，值为 1
经过压缩之后，原来需要声明大小为 63 的数组，而使用压缩后，只需要声明大小为 6 * 3 的数组，仅需 18 个存储空间。
将二维数组变成稀疏数组
如何把下面这个二维数组变成稀疏数组呢？
public class SparseArray {
public static void main(String[] args) {
// 创建一个原始的二维数组 11 * 11
// 0: 表示没有数据
int[][] array = new int[11][11];
array[3][1] = 18;
array[9][4] = 53;
array[5][3] = 99;
// 输出原始的二维数组
System.out.println("原始的二维数组~~");
//先遍历每一行，得到一个一维的整数数组
for (int[] row : array) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
生成稀疏数组
/**
* 生成稀疏数组
*
* @param array 原始数组
* @return 生成的稀疏数组
*/
private static int[][] buildSparseArr(int[][] array) {
// 将二维数组 转 稀疏数组
// 1. 先遍历二维数组 得到非0数据的个数，共有sum个非零元素
//得到 sum 的作用主要是创建数组
int sum = 0;
for (int[] ints : array) {
for (int j = 0; j < array[0].length; j++) {
if (ints[j] != 0) {
sum++;
}
}
}
// 2. 创建对应的稀疏数组
//对于每一个元素，都要创建一行进行表示，但还要存储行数、列数以及非0元素的个数
int[][] sparseArr = new int[sum + 1][3];
//先创建第一行，记录数组共有多少行、多少列，多少个非零元素
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
// 3. 遍历二维数组，将非0的值存放到 sparseArr 中
// 存储非0元素的行下标、列下标以及元素本身
int count = 0; //count 用于记录是第几个非0数据
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if (array[i][j] != 0) {
count++;
//count表示第几个非0元素，不是下标，从1开始
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = array[i][j];
}
}
}
return sparseArr;
}
遍历输出：
int[][] sparseArr = buildSparseArr(array);
// 输出稀疏数组的形式
System.out.println();
System.out.println("得到稀疏数组为~~~~");
for (int[] ints : sparseArr) {
System.out.printf("%d\t%d\t%d\t\n", ints[0], ints[1], ints[2]);
}
System.out.println();
将稀疏数组恢复为二维数组
/**
* 将稀疏数组 --》 恢复成 原始的二维数组
*
* @param sparseArr 稀疏数组
* @return 普通二维数组
*/
private static int[][] sparseArrToGeneralArr(int[][] sparseArr) {
//1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
int[][] array = new int[sparseArr[0][0]][sparseArr[0][1]];
//2. 在读取稀疏数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可
for(int i = 1; i < sparseArr.length; i++) {
array[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return array;
}
遍历输出：
int[][] array02 = sparseArrToGeneralArr(sparseArr);
// 输出恢复后的二维数组
System.out.println();
System.out.println("恢复后的二维数组");
//先取出chessArr2的每一行，得到一维数组，然后遍历数组输出
for (int[] row : array02) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
